import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{3,4};
        for(int e: s.missingTwo(nums)) {
            System.out.print(e + " ");
        }

    }

    public int[] missingTwo1(int[] nums) {
        /**
         * 消失的两个数字
         *  解法1：
         *      使用高斯求和进行计算
         *  出现问题：
         *      1，数字并非有序，需要排序，如此以来时间复杂度必定会超过O(n)*/
        // 1 预处理（时间O(1) 空间O(1)）
        Arrays.sort(nums);
        int n = nums.length;
        int fullLength = n + 2;
        int sum = (1 + fullLength) * fullLength / 2;

        // 2 求得缺失值之和（时间O(n) ）
        for(int e: nums) {
            sum -= e;
        }

        // 3 现在只要找到一个缺失值即可（时间O(n) ）
        for(int i = 0; i < n; i++) {
            // -前面出现不相等
            if(nums[i] != i+1) {
                return new int[]{i+1, sum-i-1};
            }
        }
        // -前面全相等
        return new int[]{n+1, n+2};
    }

    public int[] missingTwo2(int[] nums) {
        /**
         * 消失的两个数字
         *  解法2：
         *      使用异或操作，将全部元素异或，随后再对数组元素异或，利用同质相消的原理，最后结果一定是缺失值的异或结果
         *      目前最重要的问题就是如何分开这两个元素异或
         *      依稀记得，之前遇见这种情况，是直接区分bit位的
         *  出现问题：
         *      使用高斯 + 异或进行判断
         *      不可行，因为1^12 和 8^5的值相同，也就是说不同的两个数通过异或可能会得出相同的结果*/
        // 1 预处理
        int n = nums.length;
        int fullLength = n + 2;
        // -求得所有元素之和
        int sum = (1 + fullLength) * fullLength / 2;
        // -求得所有元素异或
        int ope = 1;
        for(int i = 2; i <= fullLength; i++) {
            ope ^= i;
        }

        // 2 求得缺失值之和 与 缺失值异或
        for(int e: nums) {
            sum -= e;
            ope ^= e;
        }

        // 3 查找值
        for(int i = 1; i <= sum/2; i++) {
            if((i^(sum-i)) == ope) {
                return new int[]{i, sum-i};
            }
        }
        return null;
    }

    public int[] missingTwo(int[] nums) {
        /**
         * 消失的两个数字
         *  解法3：
         *      使用异或操作，将全部元素异或，随后再对数组元素异或，利用同质相消的原理，最后结果一定是缺失值的异或结果
         *      目前最重要的问题就是如何分开这两个元素异或
         *      找到其为1的bit位，这个位置表示这两个缺失元素的差异处，我们只需分组异或即可
         * */
        // 1 预处理
        int n = nums.length;
        int fullLength = n + 2;
        // -求得所有元素异或
        int ope = 1;
        for(int i = 2; i <= fullLength; i++) {
            ope ^= i;
        }

        // 2 求得缺失值异或
        for(int e: nums) {
            ope ^= e;
        }

        // 3 lowbit操作
        int lowBit = ope & (-ope);

        // 4 分组求值
        int x1 = 1;
        int x2 = 1;
        for(int e: nums) {
            if((e & lowBit) == lowBit) {
                x1 ^= e;
            } else {
                x2 ^= e;
            }
        }
        for(int i = 1; i <= fullLength; i++) {
            if((i & lowBit) == lowBit) {
                x1 ^= i;
            } else {
                x2 ^= i;
            }
        }
        x1 ^= 1;
        x2 ^= 1;

        // 5 返回值
        return new int[]{x1, x2};
    }


}
